# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        # 本题关键在于之前数的和是不是大于0，如果大于0那么继续相加
        # 每加一次比较一下是否是最大的
        if len(array) == 1:
            return array[0]
        pre_sum = float('-inf')
        max_sum = float('-inf')
        for i in range(len(array)):
            if pre_sum < 0:
                pre_sum = array[i]
            else:
                pre_sum += array[i]
            if pre_sum > max_sum:
                max_sum = pre_sum
        return max_sum





test = Solution()
print(test.FindGreatestSumOfSubArray([1,4,8,-1,-3,1,-4,-6,8]))
